#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 100000
#define MAX_VALUE 10000

typedef struct Node {
    int address;
    int value;
    int next;
} Node;

typedef struct ListNode {
    int address;
    struct ListNode *next;
} ListNode;

int main() {
    int startAddress, n;
    scanf("%d %d", &startAddress, &n);

    Node nodes[MAX_NODES];
    for (int i = 0; i < n; ++i) {
        int addr, val, nxt;
        scanf("%d %d %d", &addr, &val, &nxt);
        nodes[addr] = (Node){addr, val, nxt};
    }

    // Hash table to record absolute values that have been seen
    int absValueSeen[MAX_VALUE + 1] = {0};

    // Lists to store the result and removed nodes
    ListNode *resultHead = NULL, *resultTail = NULL;
    ListNode *removedHead = NULL, *removedTail = NULL;

    int currentAddr = startAddress;
    while (currentAddr != -1) {
        Node currentNode = nodes[currentAddr];
        int absValue = abs(currentNode.value);

        if (!absValueSeen[absValue]) {
            // First occurrence, add to result list
            absValueSeen[absValue] = 1;
            ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
            newNode->address = currentNode.address;
            newNode->next = NULL;
            if (resultTail == NULL) {
                resultHead = resultTail = newNode;
            } else {
                resultTail->next = newNode;
                resultTail = newNode;
            }
        } else {
            // Duplicate, add to removed list
            ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
            newNode->address = currentNode.address;
            newNode->next = NULL;
            if (removedTail == NULL) {
                removedHead = removedTail = newNode;
            } else {
                removedTail->next = newNode;
                removedTail = newNode;
            }
        }

        currentAddr = currentNode.next;
    }

    // Output the result list
    ListNode *current = resultHead;
    while (current != NULL) {
        printf("%05d %d ", current->address, nodes[current->address].value);
        if (current->next != NULL) {
            printf("%05d\n", current->next->address);
        } else {
            printf("-1\n");
        }
        current = current->next;
    }

    // Output the removed list
    current = removedHead;
    while (current != NULL) {
        printf("%05d %d ", current->address, nodes[current->address].value);
        if (current->next != NULL) {
            printf("%05d\n", current->next->address);
        } else {
            printf("-1\n");
        }
        current = current->next;
    }

    // Free allocated memory
    current = resultHead;
    while (current != NULL) {
        ListNode *temp = current;
        current = current->next;
        free(temp);
    }

    current = removedHead;
    while (current != NULL) {
        ListNode *temp = current;
        current = current->next;
        free(temp);
    }

    return 0;
}